package algorithm.middle;

/**
 * 给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
 * 输出：9
 */
public class Largest1BorderedSquare1139 {
    /**
     * 正方形边长范围【1～数组短边】，可以数组所有元素作为左上顶点，进行边长枚举
     * 故需要每行和每列的元素前缀和，这样如果l = d 即可以为一条黑边
     *
     * @param grid
     * @return
     */
    public static int largest1BorderedSquare(int[][] grid) {
        int[][] row = new int[grid.length][grid[0].length];
        int[][] col = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (i == 0) {
                    col[i][j] = grid[i][j];
                }
                if (j == 0) {
                    row[i][j] = grid[i][j];
                }
                if (i > 0) {
                    col[i][j] = col[i - 1][i] + grid[i][j];
                }
                if (j > 0) {
                    row[i][j] = row[i][j - 1] + grid[i][j];
                }
            }
        }


        int chang = grid[0].length;
        int gao = grid.length;
        int res = 0;
        int len = Math.min(grid.length, grid[0].length);
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                for (int n = 1; n <= len; n++) {
                    if (i + n > gao) break;
                    if (j + n > chang) break;
                    //up
                    boolean up = row[i][j + n - 1] - row[i][j] + 1 == n;
                    //left
                    boolean left = col[i + n - 1][j + n - 1] - col[i][j] + 1 == n;
                    //down
                    boolean down = row[i + n - 1][j + n - 1] - row[i + n - 1][j] + 1 == n;
                    //right
                    boolean right = col[i + n - 1][j + n - 1] - col[i][j + n - 1] + 1 == n;
                    if (up && left && down && right) {
                        res = Math.max(res, n);
                    }
                }
            }
        }
        return res * res;
    }


    public static void main(String[] args) {
        int[][] aaa = {{0}};
        largest1BorderedSquare(aaa);
    }


    public int largest1BorderedSquare2(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] rs = new int[m][n + 1], cs = new int[n][m + 1];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                rs[i][j + 1] = rs[i][j] + grid[i][j]; // 每行的前缀和
                cs[j][i + 1] = cs[j][i] + grid[i][j]; // 每列的前缀和
            }
        for (int d = Math.min(m, n); d > 0; --d) // 从大到小枚举正方形边长 d
            for (int i = 0; i <= m - d; ++i)
                for (int j = 0; j <= n - d; ++j) // 枚举正方形左上角坐标 (i,j)
                    if (rs[i][j + d] - rs[i][j] == d && // 上边
                            cs[j][i + d] - cs[j][i] == d && // 左边
                            rs[i + d - 1][j + d] - rs[i + d - 1][j] == d && // 下边
                            cs[j + d - 1][i + d] - cs[j + d - 1][i] == d)   // 右边
                        return d * d;
        return 0;
    }

}
